This invention relates to discrete transforms of data, and in particular to a real-time method for bit-reversal of large size data arrays.
In information transfer systems, analog data received from a user are converted to an equivalent digital format represented by a succession of bits. Efficient digital data transmission and storage is often achieved using compression techniques. A common technique for compressing data includes converting digital data from a time domain format to a frequency domain format. Discrete transforms like the FFT (fast Fourier transform), DCT (discrete cosinus transform), IDCT (inverse discrete cosinus transform), DST (discrete sinus transform), Fast Walsh Transform (FWT), Fast Hadamard Transform (FHT), etc., take discrete inputs in one format and convert them to discrete outputs in another. For example, the FFT is typically used to transform digital data from the time domain to digital data format in the frequency domain.
Many discrete transforms are executed xe2x80x9cin placexe2x80x9d using the same memory locations for both the inputs and the outputs. This technique is used to reduce the memory needed for the execution of the transform and also to reduce the complexity of the transform algorithms. During certain steps in the FFT, and other discrete transform routines, a bit-reversed order representation of the data is produced, so that the data needs to be thereafter reversed to the normal order. Thus, the circuitry performing the discrete transform must include routines that perform complex operations such as shifting of data for bit-reversal, including transfer or moving. In digital telecommunications, bit-reversal routines are used for example for signal modulation/demodulation, signal features extraction, error detection and correction.
In general, a data terminal includes one or more Digital Signal Processors (DSP). A DSP is a special central processing unit (CPU) designed to manipulate data to perform a specific function on the input data. The DSP comprises a small internal memory for storing data and codes and also a number of internal registers for exchanging information with the external memory. DSPs generally operate in load-store mode, where the arithmetic and logic instructions use the internal registers. Data are retrieved (loaded) from the internal or external memory and loaded into the data registers using a LOAD instruction, and data are saved (stored) from the registers into the memory using a STORE instruction. Each load/store operation requires an address into the memory. These addresses are usually held in address registers. An address stored in a register is often referred to as a xe2x80x9cpointerxe2x80x9d because it points to a location in the memory, also referred as an index.
Bit-reverse and digit-reverse are routines in which the data is xe2x80x9cre-orderedxe2x80x9d by reversing the pointer value (the index) from 0 to (Nxe2x88x921), where xe2x80x9cNxe2x80x9d is the number of points to be digit/bit-reversed. The paper xe2x80x9cBit-Reverse and Digit Reverse: Linear-Time Small Look-up Table Implementation for the TMS320C6000xe2x80x9d, by Chad Courtney, published May 1998, Texas Instruments Incorporated SPRA440, describes bit reversal and digit reversal routines which sort the indices of the addresses of the data in a memory using a sorting tree. The pointers are stored in an array of 2N registers of xe2x80x9cNxe2x80x9d bits. The pointers are sorted starting with the most significant bit (MSB) of the bit-reversed order and ending with the least significant bit (LSB) so that the sorting routine is repeated for (Nxe2x88x921) times. The size of the memory necessary for performing bit/digit reversal routine is denoted with xe2x80x9cNxe2x80x9d and includes besides the memory space occupied by the indices, the space occupied by a look-up table which occupies a multiple of xe2x80x9cNxe2x80x9d bytes.
As indicated above, the bit reversal operation is effected xe2x80x9cin placexe2x80x9d on the external memory, which stores the intermediate or final results of the respective discrete transform. In the case of a uni-processor platform, bit reversal is time consuming, due mainly to the load and store operations performed on each entry of the array. This is because in most cases, the size of the available internal memory is much smaller (2 to 100 times) than the size of the array to be reversed. In addition, the array needs to be randomly accessed, which involves use of large index tables. Furthermore, a large overhead compared to the available hardware is required to meet the real-time requirement when sorting large size data arrays.
Accordingly, there is a need for a real-time method for sorting large size data arrays using bit-reversal routines on uni-processor DSP platforms.
The present invention seeks to overcome the disadvantages of the prior art associated with real-time, bit-reversal of large size data arrays on uni-processor platforms.
According to one aspect of the invention, a method for bit reversal of large data array on a uni-processor platform is provided. In a first stage, the method comprises the steps of determining the ratio K between the size Mxc3x972M of the large data array stored in an external memory, and the size Mxc3x972Q of a small array, available on an internal memory, such that K+Q=M; performing an in-place bit reversal operation for K bits of the large data array on external memory. These steps are performed by a direct memory access controller (DMA). In a second stage, a central processing unit (CPU) performs a bit reversal operation of small array on internal memory.
According to another aspect of the invention, a digital signal processor (DSP) for bit-reversal of a large data array is provided. The DSP comprises a direct memory access (DMA) controller for in-place bit reversing a number of bits of the large size data array on an external memory and a central processing unit (CPU) for performing swapping of small size sub-arrays on internal memory.
Advantageously, the two-stage method according to the invention importantly reduces the real-time implementation for sorting large size data arrays on uni-processor DSP platforms, by extensively using the external memory and avoiding a random access to the internal memory. As well, the invention provides for improved dense integration and reduced costs when used in dense wavelength division multiplexing (DWDM) systems.
The xe2x80x9cSummary of the Inventionxe2x80x9d does not necessarily disclose all the inventive features. The invention may reside in a sub-combination of the disclosed features.